/**
//设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整
//个棋盘的那两条对角线。 
//
// 注意：本题相对原题做了扩展 
//
// 示例: 
//
//  输入：4
// 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
// 解释: 4 皇后问题存在如下两个不同的解法。
//[
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
// 
// Related Topics 数组 回溯 👍 128 👎 0

*/

package com.xixi.basicAlgroithms.backtracking;

import java.util.ArrayList;
import java.util.List;

public class ID_interview_08_12EightQueensLcci {
public static void main(String[] args) {
    Solution solution = new ID_interview_08_12EightQueensLcci().new Solution();
}



//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//    定义记录结果的全局变量
    public List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        //初始化棋盘
        char[][] chart = new char[n][n];
        for(int i = 0; i < n; ++i){
            chart[i] = new char[n];
            for(int j = 0; j< n; ++j){
                chart[i][j] = '.';
            }
        }
        backTrack(n, 0, chart);

        return result;
    }

    public void backTrack(int n, int level, char[][] path){
        //判断结束条件
        if(level == n){
            //快照
            List<String> snapShot = new ArrayList<>(n);
            for(int i = 0; i < n; ++i){
                snapShot.add(new String(path[i]));
            }
            result.add(snapShot);
            return;
        }

        //决策，每一列都放一次试试
        for(int col = 0; col < n ; ++col ){
            if(isOk(n , level, col, path)){ //OKle 就往下走
                path[level][col] = 'Q'; //画上Q
                backTrack(n, level+1, path); //往下走完之后擦掉Q
                path[level][col] = '.'; //擦掉Q
            }
        }


    }

    public boolean isOk(int n, int level, int col, char[][] path){
        //左对角线向上
        int i = level - 1; //行
        int leftUp = col - 1;  //列
        int rightUp = col + 1;  //列

        while( i >=0){
            if(path[i][col] == 'Q'){
                return false; //上列被占了
            }
            if(leftUp >=0 ){
                if(path[i][leftUp] == 'Q'){
                    return false; //左上对角线被占了
                }
            }

            if(rightUp < n ){
                if(path[i][rightUp] == 'Q'){
                    return false; //右上对角线被占了
                }
            }
            --i;
            --leftUp;
            ++rightUp;
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)




}